Optimisation convexe : Définition du problème convexe sous forme standard

Un problème d'optimisation convexe sous forme standard est la base de la programmation mathématique moderne. Il est défini par une fonction objectif convexe $f_0$, des contraintes d'inégalité convexes $f_i$, et affine des contraintes d'égalité affines. En définissant le problème sur l'intersection de ces domaines $\mathcal{D} = \bigcap_{i=0}^m \text{dom } f_i$, nous assurons que tout optimum local est un optimum global.

1. Anatomie mathématique de la forme standard

Le problème est formellement énoncé comme suit :

$$\begin{aligned} &\text{minimiser} && f_0(x) \\ &\text{sous contrainte} && f_i(x) \leq 0, \quad i = 1, \dots, m \\ &&& a_i^T x = b_i, \quad i = 1, \dots, p \end{aligned}$$

L'ensemble admissible est défini par $\text{dom } F = \{x \in \text{dom } f_0 \mid f_i(x) \le 0, i = 1, \dots, m, h_i(x) = 0, i = 1, \dots, p \}$. Une exigence cruciale pour la convexité est que les contraintes d'égalité doivent être affines ($Ax = b$), car les égalités non linéaires donnent généralement des ensembles non convexes.

2. Interprétation géométrique par l'épigraphe

Le problème sous forme épigraphe nous permet d'interpréter l'optimisation de manière géométrique dans l'espace 'graphique' $(x, t)$. En introduisant une variable de relaxation $t$, on minimise $t$ sous la contrainte $(x, t) \in \text{epi } f_0$. Cela démontre que l'ensemble admissible, tout ensemble de niveau inférieur, et l'ensemble optimal sont intrinsèquement convexes.

3. Le piège entre contraintes implicites et explicites

Une erreur courante est de penser que déplacer les contraintes vers l'objectif (les rendant implicites) simplifie le problème. Or, rendre les contraintes implicites n'a pas rendu le problème plus facile à analyser ou à résoudre, même si le problème résultant est théoriquement sans contraintes. Ceci est particulièrement vrai dans le modèle Oracle (boîte noire), où nous évaluons $f(x)$ et ses dérivées à un coût sans connaître la structure explicite.

4. Applications réelles

Théorie des portefeuilles : Minimisation du risque $\text{var}(c^T x) = x^T \Sigma x$ pour 4 actifs (par exemple, Actif 1 avec un rendement de 12 % / écart-type de 20 %).
Ingénierie : Contraintes structurelles telles que $y_i = 6(i - 1/3) \frac{F}{E w_i h_i^3} + v_{i+1} + y_{i+1}$.
Probabilité : Contraintes de risque de perte $\Phi^{-1}(\beta) \leq 0$.

🎯 Principe fondamental

La condition d'optimalité pour une fonction $f_0$ différentiable est donnée par $\nabla f_0(x)^T(y - x) \geq 0$ pour tout $y$ admissible. Cela implique que le gradient doit être un hyperplan support de l'ensemble admissible au point optimal.

QUESTION 1

Pourquoi les contraintes d'égalité dans un problème d'optimisation convexe doivent-elles être affines ($Ax = b$) ?

Parce que les contraintes d'égalité non linéaires définissent généralement des ensembles non convexes.

Pour garantir que la fonction objectif reste différentiable.

Parce que le modèle Oracle ne peut pas gérer les sous-routines non linéaires.

Pour permettre l'utilisation de variables de relaxation pour la conversion des inégalités.

QUESTION 2

Dans le modèle Oracle (boîte noire), laquelle des affirmations suivantes est vraie ?

Évaluer la fonction objectif a un coût computationnel nul.

La structure explicite de la fonction est inconnue, mais nous pouvons évaluer $f(x)$ et ses dérivées.

Les contraintes implicites rendent le problème nettement plus simple à résoudre que les contraintes explicites.

La matrice de Hankel doit être diagonale pour que le modèle converge.

QUESTION 3

Qu'est-ce que l'épigraphe d'une fonction convexe $f_0$ représente dans le contexte de l'optimisation ?

L'ensemble de tous les points où le gradient est nul.

L'ensemble des points situés sur ou au-dessus du graphe de la fonction.

L'intersection de toutes les contraintes d'égalité affines.

Une combinaison linéaire de monômes à coefficients réels.

QUESTION 4

Quelle condition mathématique représente une contrainte spectrale sur la matrice $A$ étant bornée par $s$ ?

$\|A\|_2 \leq s \iff A^T A \preceq s^2 I$

$Ax = b$

$\text{var}(c^T x) = x^T \Sigma x$

$\Phi^{-1}(\beta) \leq 0$

QUESTION 5

Quel est le résultat de l'introduction de variables de relaxation à une contrainte d'inégalité $f_i(x) \le 0$ ?

Le problème devient sans contraintes.

Elle remplace l'inégalité par une contrainte d'égalité et une contrainte de non-négativité.

Elle transforme un problème convexe en un problème signomial non convexe.

L'ensemble admissible est projeté sur la matrice de Hankel.